A multi-way tree (e.g. B-tree and its variations) is widely used in a file system or a database to organize data on a storage device (e.g. disk). A typical multi-way tree may consist of a root node, intermediate nodes and leaf nodes. Generally, an upper-level node may be used to store an address of a lower-level node (e.g., disk block number), and the leaf nodes may be used to store data for an actual application. To access a leaf node, an address of a next-level node can be searched sequentially from the root node, until the address of the leaf node to be accessed is found. Besides, to access a node in a storage device, the node needs to be read from the storage device to a memory firstly, and then accessed from the memory.
In order to access a node in the multi-way tree more quickly with considering a limited memory size, some of the nodes in the multi-way tree may be cached in the memory. Typically, least recently used (LRU) algorithm can be used to swap in/out a node to/from the memory. For example, an LRU linked list may be used to link the nodes in the memory, where a head of the linked list is the most recently accessed node and a tail of the linked list is the least recently used node. If usage of the memory exceeds a predetermined threshold, one or more cached nodes starting from the tail of the linked list may be swapped out of the memory to release the pressure on the memory.